package LearnDataStructure.c_树结构.例题;

import LearnDataStructure.c_树结构.BSTNode;
import LearnDataStructure.c_树结构.有序树.二叉树.b_MyBinaryTreebyLinked;
import java.util.ArrayList;
import java.util.List;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-12 16:53
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.例题
 */
public class b_所有种数字之和 {
    public static void main(String[] args) {
        b_所有种数字之和 test = new b_所有种数字之和();
        b_MyBinaryTreebyLinked<Integer, Integer> Btree = new b_MyBinaryTreebyLinked<>();
        // Btree.insert(10,9);
        Btree.insert(6,5);
        Btree.insert(4,3);
        Btree.insert(7,6);
        Btree.insert(8,7);
        Btree.insert(9,8);
        Btree.insert(2,1);
        // Btree.insert(1,0);
        // Btree.insert(13,0);
        System.out.println(Btree);
        test.useSumTree(Btree.getRoot());//注意加的是value而不是key
    }

    private List<String> list = new ArrayList<>();

    public void useSumTree(BSTNode<Integer,Integer> root) {
        if (root == null) {
            return;
        }
        int result = 0;
        sumTree("", root);
        for (String element : list) {
            int num = Integer.parseInt(element);
            result += num;
        }
        System.out.println(result);
    }

    private void sumTree(String prefix, BSTNode<Integer, Integer> node) {
        String currentPrefix = prefix + node.value;
        if (node.left == null && node.right == null) {//递归出口
            list.add(currentPrefix);
            return;
        }
        if (node.left != null) {
            sumTree(currentPrefix, node.left);
        }
        if (node.right != null) {
            sumTree(currentPrefix, node.right);
        }
    }
}
